package io.adrainty.algorithm.leetcode.lcr;

/**
 * LCR 001. 两数相除
 * @link <a href="https://leetcode.cn/problems/xoh6Oh/description/">...</a>
 * @author AdRainty
 * @version V1.0.0
 * @since 2024/8/28 下午11:53
 */
public class LCR001 {

    public int divide(int a, int b) {
        // 溢出考虑 -2^31 / -1, 返回整数最大值
        if (a == 0x80000000 && b == -1) return 0x7fffffff;

        // 符号位
        int negative = 2;
        if (a > 0) {
            negative--;
            a = -a;
        }

        if (b > 0) {
            negative--;
            b = -b;
        }

        int result = doDivide(a, b);
        return negative == 1 ? -result : result;
    }

    private int doDivide(int a, int b) {
        int result = 0;

        while (a <= b) {
            int value = b;
            int count = 1;

            // value + value 可能会溢出
            while (value >= Integer.MIN_VALUE / 2 && value + value >= a) {
                value += value;
                count += count;
            }

            result += count;
            a -= value;
        }

        return result;
    }

}
